#include "pch.h"
#include "MaxPriorityQueue.h"


PriorityQueue::PriorityQueue(int capacity) {
	items.clear();
	items.resize(capacity+1);
	N = 0;
}

bool PriorityQueue::isEmpty() {
	return (N == 0);
}
PQ_T PriorityQueue::delMax() {
	PQ_T max = items[1];
	exch(1, N--);
	sink(1);
	return max;
}

bool PriorityQueue::less(int i, int j) {
	return (items[i] < items[j]);
}

void PriorityQueue::swim(int n) {

	while (n > 1) {
		if (less(n / 2, n)) {
			exch(n / 2, n);
		}
		else {
			break;
		}
		n /= 2;
	}
}
void PriorityQueue::sink(int n) {
	while (n * 2 <= N) {
		int maxPos = n * 2;
		if (n * 2 + 1 <= N) {
			if (less(n * 2, n * 2 + 1)) {
				maxPos = n * 2 + 1;
			}
		}
		if (less(n, maxPos)) {
			exch(maxPos, n);
		}
		else {
			break;
		}
		n = maxPos;
	}
}
void PriorityQueue::insert(PQ_T value) {
	items[++N] = value;
	swim(N);
}
void PriorityQueue::exch(int i, int j) {
	PQ_T tmp = items[i];
	items[i] = items[j];
	items[j] = tmp;
}
int PriorityQueue::size() {
	return N;
}

PriorityQueue::~PriorityQueue()
{
}
